﻿$import( "SmitearWebGL.Scene.QuadTreeNode" );
$import( "SmitearWebGL.Scene.QuadTreeRect" );

SmitearWebGL.Scene.QuadTree = Class.extend(
{
	/* * * * * * * * constructor * * * * * * * */

	init : function()
	{
		this._super();
		this._registClass( "SmitearWebGL.Scene.QuadTree" );

		/* * * * * * * * public property * * * * * * * */

		/* * * * * * * * private property * * * * * * * */

		this._worldExtents = $V3();
		this._worldScale = $V3();
		this._worldOffset = $V3();
		this._levelNodes = new Array( SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth );
		this._searchResults = new Array( SmitearWebGL.Scene.QuadTree.accommodateMembers );
		this._depth = 0;
		this._numResults = 0;
	}
	,
	isReady : function()
	{
		return this._depth && this._levelNodes != null;
	}
	,
	getSearchResults : function()
	{
		return this._searchResults.slice( 0, this._numResults );
	}
	,
	getNodeFromLevelXZ : function( level,  x,  z )
	{
		$THROW( this.isReady(), "四叉树还没有被创建" );

		if ( level >= 0 && level < this._depth )
		{
			return this._levelNodes[level][( z << level ) + x];
		}

		return null;
	}
	,
	buildByteRect : function( rect, byteRect )
	{
		byteRect.convert( rect, this._worldOffset, this._worldScale );
	}
	,
	findTreeNode : function( worldByteRect )
	{
		var arrl = this.findTreeNodeInfo( worldByteRect );
		var level = arrl[0], levelX = arrl[1], levelZ = arrl[2];

		return this.getNodeFromLevelXZ( level, levelX, levelZ );
	}
	,
	findTreeNodeInfo : function( worldByteRect )
	{
		var xPattern = worldByteRect.x0 ^ worldByteRect.x1;
		var zPattern = worldByteRect.z0 ^ worldByteRect.z1;

		var bitPattern = Math.max( xPattern, zPattern );
		var highBit = bitPattern ? SmitearWebGL.Core.Math.highestBitSet( bitPattern ) + 1 : 0;

		var level = Math.min( SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth - highBit - 1, this._depth - 1 );

		var shift = SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth - level - 1;

		var levelX = worldByteRect.x1 >> shift;
		var levelZ = worldByteRect.z1 >> shift;

		return [level, levelX, levelZ];
	}
	,
	create : function( worldBoundingBox, depth )
	{
		$THROW( ! this.isReady(), "四叉树已被创建" );
		$THROW( depth >= SmitearWebGL.Scene.QuadTree.eConstants.k_minimumTreeDepth, "无效深度值" );
		$THROW( depth <= SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth, "无效深度值" );

		this._depth = depth;
		this._worldExtents = worldBoundingBox.size();
		this._worldOffset = worldBoundingBox.minPoint();
		this._worldOffset.opposite();

		this._worldScale.x = 256.0 / this._worldExtents.x;
		this._worldScale.y = 32.0 / this._worldExtents.y;
		this._worldScale.z = 256.0  / this._worldExtents.z;

		var i, j;
		for ( i = 0; i < depth; ++ i )
		{
			var nodeCount = ( 1 << i ) * ( 1 << i );
			var quadTreeNodes = new Array( nodeCount );
			for ( j = 0; j < nodeCount; ++ j )
			{
				quadTreeNodes[j] = new SmitearWebGL.Scene.QuadTreeNode();
				quadTreeNodes[j].levelFlag.dpeth = i;
				quadTreeNodes[j].levelFlag.count = j;
			}
			this._levelNodes[i] = quadTreeNodes;
		}

		var x, z;

		for ( i = 0; i < depth; ++ i )
		{
			var levelDimension = ( 1 << i );
			var levelIndex = 0;
			for ( z = 0; z < levelDimension; ++ z )
			{
				for ( x = 0; x < levelDimension; ++ x )
				{
					this._levelNodes[i][levelIndex ++ ].setup(
					this.getNodeFromLevelXZ( i - 1, ( x >> 1 ), ( z >> 1 ) ),
					this.getNodeFromLevelXZ( i + 1, ( x << 1 ), ( z << 1 ) ),
					this.getNodeFromLevelXZ( i + 1, ( x << 1 ) + 1, ( z << 1 ) ),
					this.getNodeFromLevelXZ( i + 1, ( x << 1 ), ( z << 1 ) + 1 ),
					this.getNodeFromLevelXZ( i + 1, ( x << 1 ) + 1, ( z << 1 ) + 1 ) );
				}
			}
		}
	}
	,
	release : function()
	{
		for ( var i = 0; i < SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth; ++ i )
		{
			var nodes = this._levelNodes[i];
			for ( var j = 0; j < nodes.length; ++ j )
			{
				nodes[j].release();
				nodes[j] = null;
			}
			this._levelNodes[i] = null;
		}
		this._levelNodes = null;
		this._worldExtents = null;
		this._worldScale = null;
		this._worldOffset = null;
		this._depth = 0;
		this._searchResults.splice( 0, this._searchResults.length );
		this._searchResults = null;
		this._numResults = 0;
	}
	,
	addSceneObject : function( mesh )
	{
		this.updateSceneObject( mesh );
	}
	,
	removeSceneObject : function( node )
	{
		if ( node.getQuadTreeNode() )
		{
			node.getQuadTreeNode().removeMember( node );
			node.setQuadTreeNode( null );
		}
	}
	,
	updateSceneObject : function( mesh )
	{
		var byteRect = new SmitearWebGL.Scene.QuadTreeRect();
		this.buildByteRect( mesh.getBoundingBox().getWorldAABB(), byteRect );

		var node = this.findTreeNode( byteRect );

		$THROW( node != null, "定位节点失败" );

		node.updateMember( mesh, byteRect );
	}
	,
	buildSearchResults : function( frustumRect, nearClip, farClip )
	{
		if ( this._numResults >= SmitearWebGL.Scene.QuadTree.accommodateMembers ) return SmitearWebGL.Core.HResult.MAX_QUAD_TREE_MEMBER;

		var byteRect = new SmitearWebGL.Scene.QuadTreeRect();
		this.buildByteRect( frustumRect, byteRect );

		var yMask = SmitearWebGL.Scene.QuadTreeNode.yMask( byteRect.y0, byteRect.y1 );
		var continueSearch = true;
		var level = 0;

		while( level < this._depth && continueSearch )
		{
			var shift_count = 8 - level;
			var localRect = new SmitearWebGL.Scene.QuadTreeRect( byteRect.x0 >> shift_count,
			byteRect.x1 >> shift_count,
			0, 0,
			byteRect.z0 >> shift_count,
			byteRect.z1 >> shift_count );
			continueSearch = false;

			for ( var z = localRect.z0; z <= localRect.z1;
			++ z )
			{
				for ( var x = localRect.x0; x <= localRect.x1;
				++ x )
				{
					var node = this.getNodeFromLevelXZ( level, x, z );

					if ( node.getYMask().contain( yMask ) )
					{
						continueSearch = true;

						if ( z == localRect.z0
						|| z == localRect.z1
						|| x == localRect.x0
						|| x == localRect.x1 )
						{
							this._numResults = node.testLocalMembersForSearchResultsByRect( this._searchResults, this._numResults, yMask, frustumRect, nearClip, farClip );
						}
						else
						{
							this._numResults = node.testLocalMembersForSearchResults( this._searchResults, this._numResults, yMask, nearClip, farClip );
						}
					}
				}
			}

			++ level;
		}

		return SmitearWebGL.Core.HResult.SUCCESS;
	}
	,
	updateBeforeRender : function()
	{
		for ( var i = 0; i < SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth; ++ i )
		{
			var nodes = this._levelNodes[i];
			if ( nodes )
			{
				for ( var j = 0; j < nodes.length; ++ j )
				{
					var node = nodes[j];
					if ( node.getStatus( SmitearWebGL.Scene.QuadTreeNode.eStates.k_yMaskDirty ) )
					node.updateBeforeRender();
				}
			}
		}
	}
	,
	updateAfterRender : function()
	{
		for ( var i = 0; i < SmitearWebGL.Scene.QuadTree.eConstants.k_maximumTreeDepth; ++ i )
		{
			var nodes = this._levelNodes[i];
			if ( nodes )
			{
				for ( var j = 0; j < nodes.length; ++ j )
				{
					var node = nodes[j];
					node.updateAfterRender();
				}
			}
		}

		this._numResults = 0;
	}
}
);

SmitearWebGL.Scene.QuadTree.eConstants =
{
	k_minimumTreeDepth : 1,
	k_maximumTreeDepth : 9
}

SmitearWebGL.Scene.QuadTree.accommodateMembers = 1024;